home *** CD-ROM | disk | FTP | other *** search
/ MACD 5 / MACD 5.bin / workbench / libs / unixlib.lha / unix / src / regex.c < prev    next >
Text File  |  1996-04-27  |  9KB  |  402 lines
  1. /*
  2.  * Copyright (c) 1980 Regents of the University of California.
  3.  * All rights reserved.  The Berkeley software License Agreement
  4.  * specifies the terms and conditions for redistribution.
  5.  */
  6.  
  7. #if defined(LIBC_SCCS) && !defined(lint)
  8. static char sccsid[] = "@(#)regex.c    5.2 (Berkeley) 3/9/86";
  9. #endif /* LIBC_SCCS and not lint */
  10.  
  11.  
  12. /*
  13.  * routines to do regular expression matching
  14.  *
  15.  * Entry points:
  16.  *
  17.  *    re_comp(s)
  18.  *        char *s;
  19.  *     ... returns 0 if the string s was compiled successfully,
  20.  *             a pointer to an error message otherwise.
  21.  *         If passed 0 or a null string returns without changing
  22.  *           the currently compiled re (see note 11 below).
  23.  *
  24.  *    re_exec(s)
  25.  *        char *s;
  26.  *     ... returns 1 if the string s matches the last compiled regular
  27.  *               expression, 
  28.  *             0 if the string s failed to match the last compiled
  29.  *               regular expression, and
  30.  *            -1 if the compiled regular expression was invalid 
  31.  *               (indicating an internal error).
  32.  *
  33.  * The strings passed to both re_comp and re_exec may have trailing or
  34.  * embedded newline characters; they are terminated by nulls.
  35.  *
  36.  * The identity of the author of these routines is lost in antiquity;
  37.  * this is essentially the same as the re code in the original V6 ed.
  38.  *
  39.  * The regular expressions recognized are described below. This description
  40.  * is essentially the same as that for ed.
  41.  *
  42.  *    A regular expression specifies a set of strings of characters.
  43.  *    A member of this set of strings is said to be matched by
  44.  *    the regular expression.  In the following specification for
  45.  *    regular expressions the word `character' means any character but NUL.
  46.  *
  47.  *    1.  Any character except a special character matches itself.
  48.  *        Special characters are the regular expression delimiter plus
  49.  *        \ [ . and sometimes ^ * $.
  50.  *    2.  A . matches any character.
  51.  *    3.  A \ followed by any character except a digit or ( )
  52.  *        matches that character.
  53.  *    4.  A nonempty string s bracketed [s] (or [^s]) matches any
  54.  *        character in (or not in) s. In s, \ has no special meaning,
  55.  *        and ] may only appear as the first letter. A substring 
  56.  *        a-b, with a and b in ascending ASCII order, stands for
  57.  *        the inclusive range of ASCII characters.
  58.  *    5.  A regular expression of form 1-4 followed by * matches a
  59.  *        sequence of 0 or more matches of the regular expression.
  60.  *    6.  A regular expression, x, of form 1-8, bracketed \(x\)
  61.  *        matches what x matches.
  62.  *    7.  A \ followed by a digit n matches a copy of the string that the
  63.  *        bracketed regular expression beginning with the nth \( matched.
  64.  *    8.  A regular expression of form 1-8, x, followed by a regular
  65.  *        expression of form 1-7, y matches a match for x followed by
  66.  *        a match for y, with the x match being as long as possible
  67.  *        while still permitting a y match.
  68.  *    9.  A regular expression of form 1-8 preceded by ^ (or followed
  69.  *        by $), is constrained to matches that begin at the left
  70.  *        (or end at the right) end of a line.
  71.  *    10. A regular expression of form 1-9 picks out the longest among
  72.  *        the leftmost matches in a line.
  73.  *    11. An empty regular expression stands for a copy of the last
  74.  *        regular expression encountered.
  75.  */
  76.  
  77. /*
  78.  * constants for re's
  79.  */
  80. #define    CBRA    1
  81. #define    CCHR    2
  82. #define    CDOT    4
  83. #define    CCL    6
  84. #define    NCCL    8
  85. #define    CDOL    10
  86. #define    CEOF    11
  87. #define    CKET    12
  88. #define    CBACK    18
  89.  
  90. #define    CSTAR    01
  91.  
  92. #define    ESIZE    512
  93. #define    NBRA    9
  94.  
  95. static    char    expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
  96. static    char    circf;
  97.  
  98. static int advance(register char *, register char *);
  99. int cclass(register char *, register char, int);
  100. int backref(register int, register char *);
  101.  
  102. /*
  103.  * compile the regular expression argument into a dfa
  104.  */
  105. char *
  106. re_comp(register char *sp)
  107. {
  108.     register int    c;
  109.     register char    *ep = expbuf;
  110.     int    cclcnt, numbra = 0;
  111.     char    *lastep = 0;
  112.     char    bracket[NBRA];
  113.     char    *bracketp = &bracket[0];
  114.     static    char    *retoolong = "Regular expression too long";
  115.  
  116. #define    comerr(msg) {expbuf[0] = 0; return(msg); }
  117.  
  118.     if (sp == 0 || *sp == '\0') {
  119.         if (*ep == 0)
  120.             return("No previous regular expression");
  121.         return(0);
  122.     }
  123.     if (*sp == '^') {
  124.         circf = 1;
  125.         sp++;
  126.     }
  127.     else
  128.         circf = 0;
  129.     for (;;) {
  130.         if (ep >= &expbuf[ESIZE])
  131.             comerr(retoolong);
  132.         if ((c = *sp++) == '\0') {
  133.             if (bracketp != bracket)
  134.                 comerr("unmatched \\(");
  135.             *ep++ = CEOF;
  136.             *ep = 0;
  137.             return(0);
  138.         }
  139.         if (c != '*')
  140.             lastep = ep;
  141.         switch (c) {
  142.  
  143.         case '.':
  144.             *ep++ = CDOT;
  145.             continue;
  146.  
  147.         case '*':
  148.             if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
  149.                 goto defchar;
  150.             *lastep |= CSTAR;
  151.             continue;
  152.  
  153.         case '$':
  154.             if (*sp != '\0')
  155.                 goto defchar;
  156.             *ep++ = CDOL;
  157.             continue;
  158.  
  159.         case '[':
  160.             *ep++ = CCL;
  161.             *ep++ = 0;
  162.             cclcnt = 1;
  163.             if ((c = *sp++) == '^') {
  164.                 c = *sp++;
  165.                 ep[-2] = NCCL;
  166.             }
  167.             do {
  168.                 if (c == '\0')
  169.                     comerr("missing ]");
  170.                 if (c == '-' && ep [-1] != 0) {
  171.                     if ((c = *sp++) == ']') {
  172.                         *ep++ = '-';
  173.                         cclcnt++;
  174.                         break;
  175.                     }
  176.                     while (ep[-1] < c) {
  177.                         *ep = ep[-1] + 1;
  178.                         ep++;
  179.                         cclcnt++;
  180.                         if (ep >= &expbuf[ESIZE])
  181.                             comerr(retoolong);
  182.                     }
  183.                 }
  184.                 *ep++ = c;
  185.                 cclcnt++;
  186.                 if (ep >= &expbuf[ESIZE])
  187.                     comerr(retoolong);
  188.             } while ((c = *sp++) != ']');
  189.             lastep[1] = cclcnt;
  190.             continue;
  191.  
  192.         case '\\':
  193.             if ((c = *sp++) == '(') {
  194.                 if (numbra >= NBRA)
  195.                     comerr("too many \\(\\) pairs");
  196.                 *bracketp++ = numbra;
  197.                 *ep++ = CBRA;
  198.                 *ep++ = numbra++;
  199.                 continue;
  200.             }
  201.             if (c == ')') {
  202.                 if (bracketp <= bracket)
  203.                     comerr("unmatched \\)");
  204.                 *ep++ = CKET;
  205.                 *ep++ = *--bracketp;
  206.                 continue;
  207.             }
  208.             if (c >= '1' && c < ('1' + NBRA)) {
  209.                 *ep++ = CBACK;
  210.                 *ep++ = c - '1';
  211.                 continue;
  212.             }
  213.             *ep++ = CCHR;
  214.             *ep++ = c;
  215.             continue;
  216.  
  217.         defchar:
  218.         default:
  219.             *ep++ = CCHR;
  220.             *ep++ = c;
  221.         }
  222.     }
  223. }
  224.  
  225. /* 
  226.  * match the argument string against the compiled re
  227.  */
  228. int
  229. re_exec(register char *p1)
  230. {
  231.     register char    *p2 = expbuf;
  232.     register int    c;
  233.     int    rv;
  234.  
  235.     for (c = 0; c < NBRA; c++) {
  236.         braslist[c] = 0;
  237.         braelist[c] = 0;
  238.     }
  239.     if (circf)
  240.         return((advance(p1, p2)));
  241.     /*
  242.      * fast check for first character
  243.      */
  244.     if (*p2 == CCHR) {
  245.         c = p2[1];
  246.         do {
  247.             if (*p1 != c)
  248.                 continue;
  249.                         rv = advance(p1, p2);
  250.                         if (rv)
  251.                 return(rv);
  252.         } while (*p1++);
  253.         return(0);
  254.     }
  255.     /*
  256.      * regular algorithm
  257.      */
  258.     do
  259.                 if ((rv = advance(p1, p2)))
  260.             return(rv);
  261.     while (*p1++);
  262.     return(0);
  263. }
  264.  
  265. /* 
  266.  * try to match the next thing in the dfa
  267.  */
  268. static    int
  269. advance(register char *lp, register char *ep)
  270. {
  271.     register char    *curlp;
  272.     int    ct, i;
  273.     int    rv;
  274.  
  275.     for (;;)
  276.         switch (*ep++) {
  277.  
  278.         case CCHR:
  279.             if (*ep++ == *lp++)
  280.                 continue;
  281.             return(0);
  282.  
  283.         case CDOT:
  284.             if (*lp++)
  285.                 continue;
  286.             return(0);
  287.  
  288.         case CDOL:
  289.             if (*lp == '\0')
  290.                 continue;
  291.             return(0);
  292.  
  293.         case CEOF:
  294.             return(1);
  295.  
  296.         case CCL:
  297.             if (cclass(ep, *lp++, 1)) {
  298.                 ep += *ep;
  299.                 continue;
  300.             }
  301.             return(0);
  302.  
  303.         case NCCL:
  304.             if (cclass(ep, *lp++, 0)) {
  305.                 ep += *ep;
  306.                 continue;
  307.             }
  308.             return(0);
  309.  
  310.         case CBRA:
  311.                         braslist[(int)*ep++] = lp;
  312.             continue;
  313.  
  314.         case CKET:
  315.                         braelist[(int)*ep++] = lp;
  316.             continue;
  317.  
  318.         case CBACK:
  319.             if (braelist[i = *ep++] == 0)
  320.                 return(-1);
  321.             if (backref(i, lp)) {
  322.                 lp += braelist[i] - braslist[i];
  323.                 continue;
  324.             }
  325.             return(0);
  326.  
  327.         case CBACK|CSTAR:
  328.             if (braelist[i = *ep++] == 0)
  329.                 return(-1);
  330.             curlp = lp;
  331.             ct = braelist[i] - braslist[i];
  332.             while (backref(i, lp))
  333.                 lp += ct;
  334.             while (lp >= curlp) {
  335.                                 rv = advance(lp, ep);
  336.                                 if (rv)
  337.                     return(rv);
  338.                 lp -= ct;
  339.             }
  340.             continue;
  341.  
  342.         case CDOT|CSTAR:
  343.             curlp = lp;
  344.             while (*lp++)
  345.                 ;
  346.             goto star;
  347.  
  348.         case CCHR|CSTAR:
  349.             curlp = lp;
  350.             while (*lp++ == *ep)
  351.                 ;
  352.             ep++;
  353.             goto star;
  354.  
  355.         case CCL|CSTAR:
  356.         case NCCL|CSTAR:
  357.             curlp = lp;
  358.             while (cclass(ep, *lp++, ep[-1] == (CCL|CSTAR)))
  359.                 ;
  360.             ep += *ep;
  361.             goto star;
  362.  
  363.         star:
  364.             do {
  365.                 lp--;
  366.                                 rv = advance(lp, ep);
  367.                                 if (rv)
  368.                     return(rv);
  369.             } while (lp > curlp);
  370.             return(0);
  371.  
  372.         default:
  373.             return(-1);
  374.         }
  375. }
  376.  
  377. int
  378. backref(register int i, register char *lp)
  379. {
  380.     register char    *bp;
  381.  
  382.     bp = braslist[i];
  383.     while (*bp++ == *lp++)
  384.         if (bp >= braelist[i])
  385.             return(1);
  386.     return(0);
  387. }
  388.  
  389. int
  390. cclass(register char *set, register char c, int af)
  391. {
  392.     register int    n;
  393.  
  394.     if (c == 0)
  395.         return(0);
  396.     n = *set++;
  397.     while (--n)
  398.         if (*set++ == c)
  399.             return(af);
  400.     return(! af);
  401. }
  402.